package com.llb666.java.leetcode;

/**
 * Created by 斌~
 * 2021/4/28 17:05
 * 把n枚硬币搭建阶梯，第一层为1 第二层为2 第i层为i.
 */
public class 排列硬币 {
    public static void main(String[] args) {
        System.out.println(arrangeCoins(10));
        System.out.println(arrangeCoins2(10));
    }

    /**
     * 迭代
     * @param n 硬币总数
     * @return 阶梯数
     */
    private static int arrangeCoins(int n){
        // 1,2,3,4,  ===> 10
        for (int i = 1; i <=n ; i++) {
            n= n-i;
            if(n<=i){
                return i;
            }
        }
        return 0;
    }

    private static int arrangeCoins2(int n){
        int low = 0,high =n;
        if(low <= high){
            int mid = (high-low)/2 + low;
            int cos = ((mid+1)*mid)/2;
            if(cos == n){
                return  mid;
            }else if (cos > n){
                high =mid -1;
            }else {
                low = mid +1;
            }
        }
        return  high;
    }
}
